#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long ll;
const int sumlen=600000;

struct Hashs {
    static const int m1=998244353, m2=19260817;
    ll a, b;
} powh[sumlen+1];
bool operator==(Hashs a, Hashs b) {return a.a==b.a && a.b==b.b;}
Hashs operator+(Hashs a, int b) {return Hashs{(a.a+b)%a.m1, (a.b+b)%a.m2};}
Hashs operator-(Hashs a, Hashs b) {return Hashs{(a.a-b.a+a.m1)%a.m1, (a.b-b.b+a.m2)%a.m2};}
Hashs operator*(Hashs a, int b) {return Hashs{(a.a*b)%a.m1, (a.b*b)%a.m2};}
Hashs operator*(Hashs a, Hashs b) {return Hashs{(a.a*b.a)%a.m1, (a.b*b.b)%a.m2};}

void initPow(int n) {
    powh[0] = {1, 1};
    for (int i=1; i<=n; i++) powh[i] = powh[i-1]*27;
}

struct HashMap {
    static const int size=1949101;
    int k[size+1][2], val[size+1];

    void push(int k1, int k2, int v) {
        int p=((ll)k1*sumlen+k2)%size;
        for (; k[p][0]; p=(p+1)%size) {
            if (k[p][0]==k1 && k[p][1]==k2) break;
        }
        k[p][0]=k1, k[p][1]=k2, val[p]=v;
    }

    int get(int k1, int k2) {
        int p=((ll)k1*sumlen+k2)%size;
        for (; k[p][0]; p=(p+1)%size) {
            if (k[p][0]==k1 && k[p][1]==k2) {
                return val[p];
            }
        }
        return -1;
    }
} ans;

Hashs hpol[2*sumlen+1], *a[2*sumlen+1];
int len[2*sumlen+1];

int getAns(int x, int y) {
    int l=min(len[x], len[y]);
    for (int i=l; i>0; i--) {
        if (a[x][len[x]]-a[x][len[x]-i]*powh[i]==a[y][i]) return i;
    }
    return 0;
}

int main() {
    freopen("string.in", "r", stdin);
    freopen("string.out", "w", stdout);
    int n, q;
    scanf("%d %d", &n, &q);
    initPow(sumlen);
    a[0] = hpol;
    for (int i=1; i<=n; i++) {
        char c;
        a[i] = a[i-1]+len[i-1]+1;
        for (c=getchar(); c<'a' || c>'z'; c=getchar());
        for (; c>='a' && c<='z'; c=getchar()) {
            len[i]++;
            a[i][len[i]] = a[i][len[i]-1]*27+(c-'a'+1);
        }
    }

    for (int i=1; i<=q; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        int t=ans.get(x, y);
        if (t<0) {
            t=getAns(x, y);
            ans.push(x, y, t);
        }
        printf("%d\n", t);
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}
